Field
Various features relate to cryptography, and more particularly to methods and apparatuses for the generation and efficient storage of prime numbers.
Background
Many cryptographic security algorithms, such as the Rivest Shamir Adleman (RSA) algorithm, utilize cryptographic keys to operate. Such keys are typically generated using key generation processes that may require relatively large (e.g., 512 bit, 1,024 bit, etc.) prime numbers. However, prime number generation is a slow process and the processing time associated with prime number generation typically acts as a bottle neck in key generation processes. The processing time required is proportional to the cube of the bit length of the key to be generated by the key generation process. For example, generating 2,048 bit and 3,072 bit cryptographic keys may be 8 and 27 times slower, respectively, than generating a 1,024 bit key. In mobile device applications where power and speed constraints are pertinent, such increases in power consumption and processing time are deleterious.
According to some applications, cryptographic keys may be generated “offline” in that they are generated before they are actually needed by an application. The cryptographic keys or the prime numbers used to generate the cryptographic keys generated in such an offline manner are typically stored in memory and then delivered to application(s) on demand. In that case, the bottle neck in processing time associated with key generation described above is virtually eliminated. However, one outstanding issue with such offline key generation schemes is that the keys and/or the prime numbers used to generate the keys may be relatively large (e.g., more than 1,024 bits) and the necessary memory circuits required to store such large keys and/or prime numbers may not always be readily available. To compound the problem, regular data compression techniques are not very applicable in these cases because cryptographic keys and prime numbers have high entropy and cannot be compressed efficiently with conventional compression algorithms.
Thus, there is a need for new methods and apparatuses that aid in prime number generation and storage in order to minimize the amount of memory required to store large prime numbers for use in cryptographic security algorithms, such as RSA.